﻿// 0809train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <string>
#include <sstream>
#include <set>
#include <map>

using namespace std;

/*
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */

int solve01(vector<int>&prices)
{
	//边界情况
	//dp[0][0]=0 dp[0][1]=-prices[0]
	//dp[1][0]=max(dp[0][0],dp[0][1]+prices[1])
	//dp[1][1]=max(dp[0][1],-prices[1])

	//转移方程
	//dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
	//买入从i-2天转移
	//dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i])

	int dp_size = prices.size();
	vector<int>status_vec(2);
	vector<vector<int>>dynamic_grid(dp_size, status_vec);

	for (int i=0; i<dp_size; i++)
	{
		if (i-1==-1)
		{
			dynamic_grid[0][0] = 0;
			dynamic_grid[0][1] = -prices[0];
			continue;
		}

		if (i-2==-1)
		{
			dynamic_grid[1][0] = max(0, dynamic_grid[0][1] + prices[1]);
			dynamic_grid[1][1] = max(dynamic_grid[0][1], -prices[1]);
			continue;
		}

		//昨天没有/昨天有今天卖出
		int max_prev_0 = max(dynamic_grid[i - 1][0], dynamic_grid[i - 1][1] + prices[i]);
		dynamic_grid[i][0] = max_prev_0;

		//昨天有/昨天没有，今天买入i-2转移
		int max_prev_1 = max(dynamic_grid[i - 1][1], dynamic_grid[i - 2][0] - prices[i]);
		dynamic_grid[i][1] = max_prev_1;
		//for------
	}
	return dynamic_grid[dp_size - 1][0];
	//solve01
}


/*
 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；
 整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。
如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
 */

int solve02(vector<int>& prices, int fee)
{
	int dp_size = prices.size();
	vector<int>status_vec(2);
	vector<vector<int>>dynamic_grid(dp_size, status_vec);

	for (int i=0; i<dp_size; i++)
	{
		if (i-1==-1)
		{
			dynamic_grid[0][0] = 0;
			dynamic_grid[0][1] = -prices[0] - fee;
			continue;
		}

		//第i天没有 昨天没有/昨天有今天卖
		int max_prev_0 = max(dynamic_grid[i - 1][0], dynamic_grid[i - 1][1] + prices[i]);
		dynamic_grid[i][0] = max_prev_0;

		//第i天有 昨天有/昨天没有今天买(+fee)
		int max_prev_1 = max(dynamic_grid[i-1][1], dynamic_grid[i-1][0]-prices[i]-fee);
		dynamic_grid[i][1] = max_prev_1;
	}
	return dynamic_grid[dp_size-1][0];
	//solve02
}


/*
把同班的小朋友找出来。小朋友的编号为整数，与前一位小朋友同班用Y表示，不同班用N表示。
输入描述
输入为空格分开的小朋友编号和是否同班标志。
比如: 6/N 2/Y 3/N 4/Y，表示共4位小朋友，2和6同班， 3和2不同班，4和3同班。
其中，小朋友总数不超过999，每个小朋友编号大于0，小于等于999。不考虑输入格式错误问题。

输出描述
输出为两行，每一行记录一个班小朋友的编号，编号用空格分开。
且:
1. 编号需要按照大小升序排列，分班记录中第一个编号小的排在第一行；
2. 若只有一个班的小朋友，第二行为空行；

示例1
输入
6/N 2/Y 3/N 4/Y
输出
2 6
3 4
 */

void solve03(vector<string>&oh_vec)
{
	vector<pair<int, char>>pair_vec;
	for (auto&oh_str:oh_vec)
	{
		int split_pos = oh_str.find('/');
		string first = oh_str.substr(0, split_pos);
		string second = oh_str.substr(split_pos + 1);
		pair<int, char>oh_pair(stoi(first),second[0]);
		//cout << oh_pair.first << '_' << oh_pair.second << endl;
		pair_vec.push_back(oh_pair);
	}

	int vec_size = pair_vec.size();

	vector<bool>dynamic_vec(vec_size);
	dynamic_vec[0] = true;

	for (int i=1; i<vec_size; i++)
	{
		pair<int, char>curr_pair = pair_vec[i];

		if (curr_pair.second=='Y')
		{
			dynamic_vec[i] = dynamic_vec[i - 1];
		}
		else
		{
			dynamic_vec[i] = !dynamic_vec[i - 1];
		}
	}


	vector<int>class_1;
	vector<int>class_2;

	for (int i=0; i<vec_size; i++)
	{
		pair<int, char>curr_pair = pair_vec[i];
		if (dynamic_vec[i])
		{
			class_1.push_back(curr_pair.first);
		}
		else
		{
			class_2.push_back(curr_pair.first);
		}
	}
	sort(class_1.begin(), class_1.end());
	

	if (class_2.empty())
	{
		for (auto&num:class_1)
		{
			cout << num << ' ';
		}
		cout << '\n';
		return;
	}

	sort(class_2.begin(), class_2.end());

	if (class_1[0]<=class_2[0])
	{
		for (auto& num : class_1)
		{
			cout << num << ' ';
		}
		cout << '\n';
		for (auto& num : class_2)
		{
			cout << num << ' ';
		}
		return;
	}
	for (auto& num : class_2)
	{
		cout << num << ' ';
	}
	cout << '\n';
	for (auto& num : class_1)
	{
		cout << num << ' ';
	}

	//solve03
}


/*
 1获取该轮牌面，则其总分数加上该轮牌面分数，为其新的总分数
 2面直接跳到下一轮，此时将当前总分数还原为3轮前的总分数，
 若当前轮次小于等于3（即在第1、2、3轮选择跳过轮次），则总分数置为0
 */

void solve04(vector<int>&prices)
{
	int dp_size = prices.size();
	vector<int>status_vec(2);
	vector<vector<int>>dynamic_grid(dp_size, status_vec);

	
	for (int i=0; i<dp_size;i++)
	{
		if (i==0)
		{
			dynamic_grid[0][0] = 0;
			dynamic_grid[0][1] = prices[0];
			continue;
		}

		if (i>0&&i<=2)
		{
			//重置的情况
			dynamic_grid[i][0] = 0;
			int max_prev = max(dynamic_grid[i - 1][0], dynamic_grid[i - 1][1]);
			dynamic_grid[i][1] = max_prev + prices[i];
			continue;
		}

		//0重置，回到3轮前
		dynamic_grid[i][0]= max(dynamic_grid[i - 3][0], dynamic_grid[i - 3][1]);
		//1选择
		int max_prev = max(dynamic_grid[i - 1][0], dynamic_grid[i - 1][1]);
		dynamic_grid[i][1] = max_prev + prices[i];

		//for------
	}

	//for (auto&mini_vec:dynamic_grid)
	//{
	//	cout << mini_vec[0] << '_' << mini_vec[1] << endl;
	//}
	int result = max(dynamic_grid[dp_size - 1][0], dynamic_grid[dp_size - 1][1]);
	cout << result;
	//solve04
}


int main()
{
	{
		//1,-5,-6,4,3,6,-2 11
		//vector<int>prices = { 1,-5,-6,4,3,6,-2 };
		vector<int>prices;
		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		string token;
		while (getline(oh_sstream,token,','))
		{
			prices.push_back(stoi(token));
		}
		//for (auto&num:prices)
		//{
		//	cout << num << ' ';
		//}

		solve04(prices);

		return 0;
	}


	{
		//6/N 2/Y 3/N 4/Y
		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		string token;
		vector<string>oh_vec;
		while (oh_sstream>>token)
		{
			oh_vec.push_back(token);
		}

		//for (auto&str:oh_vec)
		//{
		//	cout << str << ' ';
		//}

		//vector<string>oh_vec = {"6/N","2/Y","3/N","4/Y"};
		solve03(oh_vec);
		return 0;
	}

	{
		//prices = [1,3,2,8,4,9], fee = 2 8
		vector<int>prices = { 1,3,2,8,4,9 };
		int fee = 2;
		cout << solve02(prices, fee);
		return 0;
	}

	//prices = [1,2,3,0,2] 3
	vector<int>prices = { 1,2,3,0,2 };
	cout << solve01(prices);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
